#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;


//int main()
//{
//	int ar[] = { 5, 3, 4, 1, 8, 7, 9 };
//	int const n = sizeof(ar) / sizeof(ar[0]);
//	int dp[n ] = { 0 };
//	dp[0] = 1;
//	int maxval = dp[0];
//	for (int i = 1; i < n; ++i)
//	{
//		for (int j = 0; j < i; ++j)
//		{
//			if (ar[i] > ar[j])
//			{
//				dp[i] = 1 + dp[j];
//				if (dp[i] > maxval)
//				{
//					maxval = dp[i];
//				}
//			}		
//		}
//		if (dp[i] == 0)
//		{
//			dp[i] = dp[i - 1];
//		}
//	}
//
//	cout << maxval << endl;
//	for (int v : dp)
//	{
//		cout << v << " ";
//	}
//	cout << endl;
//
//	system("pause");
//	return 0;
//}